#include <bits/stdc++.h>
using namespace std;

#define MAXN 1000001

class PA{
private:
    int size, idx, rt[MAXN];
    struct Segmenttree {
        int lc, rc, val;
    } tr[MAXN * 32];
    int build(int s, int t, vector<int>& nums){
        int x = ++idx;
        tr[x].val = 0;
        if (s == t) {
            tr[x].val = nums[s];
            return x;
        }
        int mid = (s + t) >> 1;
        tr[x].lc = build(s, mid, nums), tr[x].rc = build(mid + 1, t, nums);
        return x;
    }
    int update(int cur, int l, int r, int x, int s){
        int k = ++idx;
        tr[k] = tr[cur];
        if (l == r) {
            tr[k].val = s;
            return k;
        }
        int mid = (l + r) >> 1;
        if (x <= mid)
            tr[k].lc = update(tr[k].lc, l, mid, x, s);
        else
            tr[k].rc = update(tr[k].rc, mid + 1, r, x, s);
        return k;
    }
    int& query(int cur, int l, int r, int k){
        if (l == r)
            return tr[cur].val;
        int mid = (l + r) >> 1;
        if (k <= mid)
            return query(tr[cur].lc, l, mid, k);
        else
            return query(tr[cur].rc, mid + 1, r, k);
    }

public:
    int cnt;
    PA(vector<int>& nums)
    {
        idx = 0;
        size = nums.size();
        rt[0] = build(1, size, nums);
        cnt = 0;
    }
    void update(int l, int x, int s) {
        rt[++cnt] = update(rt[l], 1, size, x, s);
    }
    int& operator()(int l, int k) {
        rt[++cnt] = rt[l];
        return query(rt[l], 1, size, k);
    }
};

int n, m;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    vector<int> nums(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> nums[i];
    PA pa(nums);
    for (int i = 1; i <= m; i++) {
        int l, r, k, type;
        cin >> l >> type;
        if (type == 2) {
            cin >> r;
            cout << pa(l, r) << endl;
        } else {
            cin >> r >> k;
            pa.update(l, r, k);
        }
    }
    return 0;
}